"""
题目：判断一个无向图中是否存在环。


具体步骤：
初始化：用集合visited记录已访问的顶点。
DFS 辅助函数：
1:标记当前顶点为已访问。
2:遍历当前顶点的所有邻接顶点：
    若邻接顶点未访问：递归访问该邻接顶点，并将当前顶点记为其父顶点。
    若邻接顶点已访问，且该顶点不是当前顶点的父顶点：说明存在环（因为这条边不是 “从父顶点过来的边”，而是形成了环的边）。
3:处理非连通图：遍历所有顶点，若存在未访问的顶点（属于新的连通分量），从该顶点开始 DFS，确保所有连通分量都被检查。
4:结果判断：若任何一次 DFS 检测到环，返回True；全部遍历完未发现环，返回False。


测试验证
对 “有环图”（如 1-2-3-1），DFS 会检测到非父顶点的已访问邻接顶点，返回True。
对 “无环图”（如树结构 1-2-3、1-2-4），所有已访问的邻接顶点都是父顶点，无环，返回False。


补充：
在 Python 中，字典对象对 key 进行遍历时，第一个取出的 key 不一定是最初第一个放进去的 key，这与 Python 版本和字典的实现机制有关：
Python 3.6 之前：字典是无序的，遍历 key 时的顺序完全由哈希表的存储结构决定，与插入顺序无关，因此无法保证第一个取出的是最初插入的第一个 key。
Python 3.6 及之后：字典引入了 “插入顺序保留” 特性（正式成为语言规范是在 Python 3.7），即遍历 key 时的顺序与插入顺序一致。此时，正常情况下第一个取出的 key 就是最初第一个插入的 key。
但需要注意几个例外情况：
若对字典进行过删除操作，可能会影响后续插入元素的遍历顺序（内部会复用被删除元素的哈希槽位）。
若插入的 key 发生哈希冲突，且触发了字典的扩容或重排，理论上可能导致顺序微调，但这种情况对用户是透明的，且仍会保证 “逻辑插入顺序”。
总结：在 Python 3.7+ 中，无删除操作的情况下，遍历字典 key 时第一个取出的是最初第一个插入的 key；但在更早的版本或有删除操作时，无法保证这一点。

"""

class Graph:
    def __init__(self, is_directed=False):
        self.vertices = {}
        self.is_directed = is_directed

    def add_vertex(self, vertex):
        if vertex not in self.vertices:
            self.vertices[vertex] = []

    def add_edge(self, v1, v2):
        self.add_vertex(v1)
        self.add_vertex(v2)
        self.vertices[v1].append(v2)
        if not self.is_directed:
            self.vertices[v2].append(v1)

    """检测无向图中是否存在环（DFS实现）"""
    def has_cycle(self):
        visited = set()

        def dfs(vertex, parent):
            # 标记当前顶点为已访问
            visited.add(vertex)
            # 检查所有邻接顶点
            for neighbor in self.vertices[vertex]:
                # 如果邻接顶点未访问，递归检查
                if neighbor not in visited:
                    if dfs(neighbor, vertex):
                        return True
                # 如果邻接顶点已访问且不是父顶点，说明存在环!!!
                elif neighbor != parent:
                    return True
            return False

        # 检查所有连通分量
        for vertex in self.vertices:
            if vertex not in visited:
                if dfs(vertex, -1):  # -1表示没有父顶点 因为各个连通分量第一个顶点一定是没有父节点的
                    return True
        return False  # 未发现环



# 测试
# 有环图 (1-2-3-1)
graph1 = Graph()
graph1.add_edge(1, 2)
graph1.add_edge(2, 3)
graph1.add_edge(3, 1)
print(graph1.has_cycle())  # 输出: True

# 无环图 (树结构)
graph2 = Graph()
graph2.add_edge(1, 2)
graph2.add_edge(2, 3)
graph2.add_edge(2, 4)
print(graph2.has_cycle())  # 输出: False
